package com.chilly.linkedlist;

/**
 * 234. 回文链表
 * <p>
 * Created by Chilly Cui on 2020/12/1.
 */
public class PalindromeLinkedList {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;

        System.out.println(new Solution().isPalindrome(listNode));

    }


    static class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head==null) return true;

            // 1、找到前半部分链表的尾节点
            ListNode firstHalfEnd = endOfFirstHalf(head);
            // 2、反转后半部分链表
            ListNode secondHalfStart = reverseListNode(firstHalfEnd.next);

            //3、判断是否回文
            ListNode p1 = head;
            ListNode p2 = secondHalfStart;
            boolean res = true;
            while (res && p2 != null) {
                if (p1.val != p2.val) {
                    res = false;
                }
                p1 = p1.next;
                p2 = p2.next;
            }

            //4、还原链表并返回结果
            firstHalfEnd.next = reverseListNode(secondHalfStart);
            return res;
        }

        // 1、找到前半部分链表的尾节点
        public ListNode endOfFirstHalf(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

        // 2、反转后半部分链表
        public ListNode reverseListNode(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }

    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }
    }
}
